#include "bt_data.h"
#include "btree.h"
#include "Error.h"
#include "trend.h"

#include <stdlib.h>

/* Create a BTreeNode element */
static BTreeNode btree_create_node (BTData data)
{
	BTreeNode n;

	if ((n = (BTreeNode) malloc (sizeof (struct _btree_node))) == NULL)
		Die ("Failed to allocate space for binary tree node (key: %s)\n", 
			data->key);

	n->data = data;
	n->left = NULL;
	n->right = NULL;
	n->parent = NULL;
	
	return n;
}

BTree btree_init (BTData data) 
{
	BTree t;
	BTreeNode rn;

	if ((t = (BTree) malloc (sizeof (struct _btree))) == NULL)
		Die ("Failed to allocate space for binary tree\n");

	rn = btree_create_node (data);
	t->root = rn;
	t->size = 1;

	return t;
}

int btree_insert (BTree tree, char * key, FreqField field)
{
	int keycmp, l;
	BTreeNode node, parent;

	l = 0;
	parent = NULL;
	node = tree->root;

	/* Iterate through the tree until we reach a leaf node */
	while (1) {
		if (node == NULL && parent != NULL) {
			node = btree_create_node (btdata_create (key, field));
			if (l == 1)
				parent->left = node;
			else
				parent->right = node;
			node->parent = parent;
			tree->size++;
			return 0;
		} else {
			keycmp = btdata_keycmp (key, node->data->key);
			if (keycmp < 0) {
				l = 1;
				parent = node;
				node = node->left;
			} else if (keycmp > 0) {
				l = 0;
				parent = node;
				node = node->right;
			} else {
				btdata_increment (node->data, field);
				return 1;
			}
		}
	}

	return -1;
}

BTreeNode btree_lookup (BTree tree, char *key)
{
	int keycmp;
	BTreeNode node;

	node = tree->root;

	while (node != NULL) {
		keycmp = btdata_keycmp (key, node->data->key);
		if (keycmp == 0)
			return node;
		else if (keycmp < 0)
			node = node->left;
		else
			node = node->right;
	}

	return NULL;
}

BTData btree_remove (BTree tree, char *key)
{
	BTData data;
	BTreeNode re, min;

	/* Get node for specific key value */
	if ((re = btree_lookup (tree, key)) == NULL)
		return NULL;

	data = re->data;

	/* Removal of a leaf node */
	if (re->left == NULL && re->right == NULL) {
		/* Update parent pointer */
		if (re->parent->left == re)
			re->parent->left = NULL;
		else
			re->parent->right = NULL;
		free (re);
	} 
	/* With a left subtree but no right subtree - replace node 
	 * with left subtree */
	else if (re->left != NULL && re->right == NULL) {
		if (re->parent->left == re)
			re->parent->left = re->left;
		else
			re->parent->right = re->left;
		free (re);
	}
	/* With a right subtree but no left subtree - replace node
	 * with right subtree */
	else if (re->left == NULL && re->right != NULL) {
		if (re->parent->left == re)
			re->parent->left = re->right;
		else
			re->parent->right = re->right;
		free (re);
	}
	/* Both left and right subtree */
	else {
		/* Find the minimum in the right subtree */
		min = re->right;
		while (min != NULL)
			min = min->left;
		/* Swap data */
		re->data = min->data;
		/* Check to see if min has a right subtree, replace min
		 * with it if that is the case, otherwise just free */
		if (min->right != NULL)
			min->parent->left = min->right;
		else
			min->parent->left = NULL;
		free (min);
	}
	
	return data;
}

/* Frees shit */
static void btree_iterative_free (BTreeNode node, TrendingList list)
{
	BTreeNode c, p;
	c = node;

	while (c != NULL) {
		if (c->left != NULL) {
			c = c->left;
		} else if (c->right != NULL) {
			c = c->right;
		} else {
			p = c->parent;
			
			/* MODIFICATION: Here we attempt to insert the data point into
			 * the statistics table (by doing this we don't have to traverse
			 * the list four times. */
			trend_insert (list, c->data->freq, c->data->key);
			
			if (p == NULL)
				return;

			if (c == p->left)
				p->left = NULL;
			else
				p->right = NULL;

			btdata_free (c->data);
			free (c);
			c = p;
		}
	}
}

/* This function has been modified so that it calculates the
 * frequency differences as it deallocates all the memory in 
 * the binary tree. */
void btree_free (BTree *tree, TrendingList list)
{
	BTree t;

	t = *tree;

	/* If we have a left subtree from the root pass it here, 
	 * else pass the right subtree (we are guaranteed to have
	 * at least one */
	if (t->root->left != NULL)
		btree_iterative_free (t->root->left, list);
	else
		btree_iterative_free (t->root->right, list);

	free (t);
}

